Motion compensation is widely used in digital video processing algorithms to exploit temporal redundancy in an effort to produce high-quality results. An example of video processing is frame interpolation, used for standards conversion as well as for generation of slow and fast motion in motion picture film/video post-production. In frame interpolation, direct temporal interpolation, i.e. without using motion information, results either in blurring or temporal aliasing when there is relative motion between objects from frame-to-frame. Motion-compensated interpolation, on the other hand, is capable of producing results without blur and aliasing.
The success of motion-compensated interpolation hinges on the accuracy of the motion information. Because motion estimation is an underdetermined problem, it relies on a priori constraints and information about the motion vector field (e.g. smoothness), the image intensity, and models for the 3-D-to-2-D projection. When such constraints becomes invalid, motion estimation becomes inaccurate. When a background is occluded with an object moving across the background, fundamental constraints such as image intensity conservation (the optical flow constraint), used in motion estimation, becomes invalid. At the boundaries of the occluded regions, corresponding to object boundaries, smoothness of the motion field is invalid since motion of occluding objects may be significantly different. Occlusions manifest themselves as covered and uncovered regions, or self occlusions due to local deformation in non-rigid objects. Of particular interest for the subject invention are occlusions that are due to covered/uncovered regions, assuming that object deformations are sufficiently small. A depiction of such regions for a hypothetical 1-D case is given in FIGS. 1A and 1B.
FIG. 1A is a depiction of an occlusion in a 1-D image. As the rectangular object 10 in Frame 1 at time t.sub.P, moves against a stationary background 12 to a new location indicated by the location of the rectangular object 10' in Frame 2, at time t.sub.Q, FIG. 1B, it covers region 16 and uncovers region 14. The uncovered region 14 is absent at time t.sub.P and the covered region 16 is absent at time t.sub.Q. The 1-D example is shown for simplicity with the understanding that 2-D and 3-D occlusions may also occur.
FIG. 2 illustrates an Intermediate Frame, occurring at time t, wherein the region 16 is partially covered and the region 14 is partially uncovered by the rectangular object 10". In other words, the object 10 moved from its position in Frame 1 to the position shown in the Intermediate Frame to its final position shown in Frame 2. Applying linear trajectories 20 between like points at times t.sub.P and t.sub.Q. provides information about the image at time t. To be noted: If the time period between t.sub.P and t.sub.Q is great, any non-linear motion of the rectangular object 10 at time t will not be accurately detected resulting in an inaccurate Intermediate Frame determination. In a like manner, if the object 10 linearly moved to, for example, the far left and linearly back to the position shown in Frame 2, the Intermediate Frame would not represent that motion. Therefore, the time between t.sub.P and t.sub.Q must be relatively small for accurate results when using the present algorithm. Applying motion-compensated, bi-directional interpolation along the linear motion trajectories 20 results in occluded regions 18 in the intermediate frame, denoted by ellipses. Image intensities for the occluded regions are copied from the appropriate existing frame. That is, for the occluded region 18, the image intensities are copied from Frame 2, and for the occluded region 18' image intensities are copied from Frame 1. The trajectories 20 shown are ideal trajectories assuming exact motion estimation.
In summary then, using motion-compensated frame interpolation, a frame at an intermediate time instance, t, is interpolated from existing frames that are captured at times t.sub.P and t.sub.Q, where t.sub.P &lt;t&lt;t.sub.Q. The linear motion trajectories 20 (vectors) are estimated between the existing Frames 1 and 2 such that they describe linear trajectories passing through pixel locations at the missing Intermediate Frame. FIG. 2 assumes the ideal case where motion vectors are accurate and the occluded regions 18 are accurately detected and handled. For linear motion trajectories (vectors) corresponding to non-occluded regions a linear combination (e.g. a weighted average) of the two image values at times t.sub.P and t.sub.Q is used to estimate the missing pixel value through which the associated vector passes. In uncovered regions of the Intermediate Frame, background intensity values from the future frame, Frame 2, are taken as the estimates for the missing pixels. Conversely for covered regions the background intensity values for the past frame Frame 1 are taken as estimates for the missing pixel values. This is what is meant by "occlusion handling" in the context of frame interpolation.
The accuracy of motion estimation and detection of occlusion regions are important practical problems that have been addressed. See, for example, Philippe Robert, "motion compensating interpolation considering occluded, appearing and disappearing areas", Signal Processing of HDTV, III, H. Yasuda and Chiariglione (Eds.), pp. 329-341, Elsevier Publishers, Amsterdam, 1991; and M. Bierling and R. Thoma, "Motion-compensating interpolation considering covered and uncovered background", Signal Processing: Image Communication, pp. 191-212, 1989. In addition, inaccuracies in motion estimation are not limited to only occluded regions. In almost all motion estimation algorithms, the problems within the occluded region propagate to regions outside the occluded region, adversely affecting the estimates immediately outside the occluded region. This case is depicted in FIG. 3. The case of FIG. 3 should be viewed as a non-ideal version of the case shown in FIG. 2 and represents what happens in practice. The regions 22 and 22' containing the occluded regions 18 and 18', respectively, at the Intermediate Frame location of the rectangular object 10" over which motion estimates are inaccurate are designated "bad regions," respectively. In practice, motion estimates are inaccurate within "bad regions", containing the occluded regions 18 and 18' and the immediate neighborhood.
The origin of "bad regions" can be explained as follows: At occluded region boundaries, the motion vector field should not be smooth, however the optical flow constraint is valid. On the other hand, within the occluded region, the optical flow constraint is invalid, but the motion vector field is smooth. Therefore, a successful algorithm has to enforce/suppress these two constraints at the appropriate locations at and around the occluded regions. Most algorithms are incapable of doing so since they tend to enforce these constraints with a fixed relative strength for the entire image region. The Fogel algorithm (see S. Fogel, "The estimation of velocity vector fields from time-varying image sequences, Computer Vision Graphic and Image Processing: Image Understanding, vol. 53, pp. 253-287, 1991), on the other hand, deals with occlusions using an adaptive mechanism that attempts to detect occluded regions and to adjust the relative strengths of these two constraints. Detection of occluded regions is based on implicit detection of image intensity transitions (i.e. edges) and gradients of the motion vector field. Because detection of occluded regions is itself a difficult problem, the Fogel algorithm may be unable, for instance, to turn off the smoothness.sub.-- constraint at the exact position of the occlusion boundary. In fact, in certain cases, detection of edges may be rather difficult for the eye of an observer. This causes the propagation of estimation errors into what has been called the "bad regions" of FIG. 3.
There is a need therefore for an object-based method to accurately determine occluded regions, to remove the bad regions, and to perform appropriate interpolation of the Intermediate Field at occluded regions.